package com.LC._22;

import java.util.ArrayList;
import java.util.List;

class Solution {
    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {

        _generate(0, 0, n, "");
        return res;
    }

    private void _generate(int left, int right, int n, String s) {
        //先写终止条件
        if (left ==n && right ==  n) {
            System.out.println(s);
            res.add(s);
            return ;//每一个满足条件的递归return掉
        }
        ////////////////逻辑层
//        res.add(s);
        //总共调用递归次数 二的六次方
        //从最外层开始向里调用
        if (left < n) {
            _generate(left+1, right , n, s + "(");//递归到最深层时程序开始向下走
        }
        if(right<left){
            //从最深层开始向外调用
            _generate(left , right +1, n, s + ")");
        }

    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.generateParenthesis(3));
    }
}
